#include <sys/time.h>

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

// for each bar (height[i]) in map, 
// how much water it can contain depends on height[i] and the largest value before (left) and after height[i] (right)
// area i = min(left, right) - height[i] (second largest value - height[i])
// So, we use two pointers to scan the map, one scan from left to right, one scan from right to left.
// At each step:
//     Update the second larget value(second) up to now;  
//     Calculate arear i = second - height[i];
//     Update the smaller one.

int trap(vector<int>& height) {
  int left = 0;
  int right = height.size()-1;
  if(right < 2) 
    return 0;
  int leftMax = height[left];
  int rightMax = height[right];
  int second = 0;
  int area = 0;
  while(left < right) {
    leftMax = max(leftMax, height[left]);
    rightMax = max(rightMax, height[right]);
    second = min(leftMax, rightMax);
    if(height[left] < height[right]) {
      area += second - height[left];
      left++;
    } else {
      area += second - height[right];
      right--;
    }
  }
  return area;

}



int main(int argc, char* argv[]) {

  struct  timeval    tv1, tv2;
  struct  timezone   tz;
  int time1 = gettimeofday(&tv1, &tz);

  vector<int> height = {5,1,2,1,2,5};
  int ret  = trap(height);
  cout << "ret:" << ret << endl ;
  //func();

  int time2 = gettimeofday(&tv2, &tz);
  cout << "time consuming local machine:" << endl
    << tv2.tv_usec - tv1.tv_usec 
    << "us" << endl;


  return 0;
}
